package hu;


import java.util.Scanner;

public class hu16 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();
        String[] str = new String[m];
        for (int i = 0; i < m; i++) {
            str[i] = sc.nextLine();
        }
        int[] dp = new int[N + 1];
        for (int i = 0; i < m; i++) {
            String sp[] = str[i].split(" ");
            if(Integer.parseInt(sp[2]) != 0){
                String sp1[] = str[Integer.parseInt(sp[2]) - 1].split(" ");
                for (int j = N; j >= Integer.parseInt(sp[0]) + Integer.parseInt(sp1[0]); j--) {
                    int value = dp[j - Integer.parseInt(sp[0]) - Integer.parseInt(sp1[0])] +
                            (Integer.parseInt(sp[0]) * Integer.parseInt(sp[1])) + (Integer.parseInt(sp1[0]) * Integer.parseInt(sp1[1]));
                    if(dp[j] < value) {
                        dp[j] = value;
                        for (int k =  i + 1; k < m; k++) {
                            String sp2[] = str[k].split(" ");
                            if(Integer.parseInt(sp2[2]) == Integer.parseInt(sp[2])){
                                sp2[2] = "0";
                            }
                        }
                    }

                }
            }
            else{
                for (int j = N; j >= Integer.parseInt(sp[0]) ; j--) {
                    dp[j] = Math.max(dp[j], dp[j - Integer.parseInt(sp[0])] + (Integer.parseInt(sp[0]) * Integer.parseInt(sp[1])));
                }
            }

        }
        System.out.println(dp[N]);
    }
}
/*
50 5
20 3 5
20 3 5
10 3 0
10 2 0
10 1 0

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
 */